package com.kevinkk.stackandqueue;

import java.util.Deque;
import java.util.ArrayDeque;

/**
 * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
 * 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
 * 返回 滑动窗口中的最大值 。
 */

/**
 * 设计一个队列 让其队头永远存储着整个队列中的最大值
 * 那么滑动窗口的过程中，只需要对这个队列进行操作即可，每次从队列中取出队头元素即可
 */
public class SlidingWindowMaximum {
    class Myque {
        Deque<Integer> que = new ArrayDeque<>();
        // 插入元素时，就要和队列中的元素比较，将小的元素都删除
        public void push(int val) {
            while (!que.isEmpty() && val > que.peekLast())
                que.removeLast();
            que.addLast(val);
        }
        // 删除元素时，小的元素不用处理，因为在插入过程中就已经被删除掉了
        public void pop(int val) {
            if (val == que.peekFirst())
                que.removeFirst();
        }

        public int peek() {
            return que.peekFirst();
        }
    }

    class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            int[] res = new int[nums.length - k + 1];
            Myque que = new Myque();
            for (int i = 0; i < k; i++)
                que.push(nums[i]);
            int index = 0;
            res[index++] = que.peek();
            for (int i = k; i < nums.length; i++) {
                que.pop(nums[i - k]);
                que.push(nums[i]);
                res[index++] = que.peek();
            }

            return res;
        }
    }

}
